﻿//566. 重塑矩阵
//在 MATLAB 中，有一个非常有用的函数 reshape ，它可以将一个 m x n 矩阵重塑为另一个大小不同（r x c）的新矩阵，但保留其原始数据。
//给你一个由二维数组 mat 表示的 m x n 矩阵，以及两个正整数 r 和 c ，分别表示想要的重构的矩阵的行数和列数。
//重构后的矩阵需要将原始矩阵的所有元素以相同的 行遍历顺序 填充。
//如果具有给定参数的 reshape 操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** matrixReshape(int** mat, int matSize, int* matColSize, int r, int c, int* returnSize, int** returnColumnSizes)
{
    int m = matSize;
    int n = matColSize[0];
    if (m * n != r * c)//如果矩阵元素无法一一对应，则返回原始矩阵
    {
        *returnSize = matSize;
        *returnColumnSizes = matColSize;
        return mat;
    }
    int** ret = malloc(sizeof(int*) * r);
    *returnSize = r;//行
    *returnColumnSizes = malloc(sizeof(int) * r);//用于保存矩阵每行元素数量
    //给二维数组ret开辟空间
    for (int i = 0; i < r; i++)
    {
        (*returnColumnSizes)[i] = c;//矩阵每行保存c个元素
        ret[i] = malloc(sizeof(int) * c);
    }
    //对于 x∈[0,mn)
    //第 x 个元素在nums 中对应的下标为 (x / n,x % n)，
    //而在新的重塑矩阵中对应的下标为 (x / c,x % c)
    for (int x = 0; x < m * n; x++)
    {
        ret[x / c][x % c] = mat[x / n][x % n];
    }
    return ret;
}






//118. 杨辉三角
//给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
//在「杨辉三角」中，每个数是它左上方和右上方的数的和。


/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
//returnColumnSizes是一个数组，数组内保存的是每行元素的长度
int** generate(int numRows, int* returnSize, int** returnColumnSizes)
{
    int** ret = malloc(sizeof(int*) * numRows);
    *returnSize = numRows;
    *returnColumnSizes = malloc(sizeof(int) * numRows);
    for (int i = 0; i < numRows; i++)
    {
        (*returnColumnSizes)[i] = i + 1;
        ret[i] = malloc(sizeof(int) * (i + 1));
        ret[i][0] = ret[i][i] = 1;
        for (int j = 1; j < i; j++)
        {
            ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
        }
    }
    return ret;
}